#include "buddy_system.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

NODE* nodes = NULL;
int free_list[FREE_LIST_LENGTH];
int hash[HASH_LENGTH];

int global_node_id = 0;
int node_pool_horizon = 0;
int node_pool[NODE_POOL_SIZE];

static void hash_insert(int, int);
static int hash_delete(int);
static int alloc_node_pool();
static void free_node_pool(int);
static int get_free_list(int);
static void put_free_list(int);
static void delete_free_list_by_id(int);

static void hash_insert(int disk_location, int node_id)
{
	int hash_id, cur_id;
	int* pre_ptr;

	hash_id = disk_location % HASH_MOD;
	nodes[node_id].used = 1;
	nodes[node_id].ptr_disk = disk_location;
	nodes[node_id].flist_pre = PTR_UNAVAILABLE;
	nodes[node_id].flist_suc = PTR_UNAVAILABLE;

	if (hash[hash_id] == PTR_UNAVAILABLE)
	{
		hash[hash_id] = node_id;
		return;
	}

	cur_id = hash[hash_id];
	do
	{
		if (disk_location > nodes[cur_id].ptr_disk)
		{
			pre_ptr = &nodes[cur_id].flist_suc;
			cur_id = nodes[cur_id].flist_suc;
		}
		else if (disk_location < nodes[cur_id].ptr_disk)
		{
			pre_ptr = &nodes[cur_id].flist_pre;
			cur_id = nodes[cur_id].flist_pre;
		}
	}while (cur_id != PTR_UNAVAILABLE);
	*pre_ptr = node_id;
}

static int hash_delete(int location)
{
	int node_id, hash_id, result_id, cur_id;
	int* pre_ptr;
	int right_id, right_left_id;

	hash_id = location % HASH_MOD;
	pre_ptr = &hash[hash_id];
	cur_id = hash[hash_id];
	if (cur_id == PTR_UNAVAILABLE) return HASH_DELETE_FAIL;

	while (cur_id != PTR_UNAVAILABLE)
	{
		if (location > nodes[cur_id].ptr_disk)
		{
			pre_ptr = &nodes[cur_id].flist_suc;
			cur_id = nodes[cur_id].flist_suc;
			if (cur_id == PTR_UNAVAILABLE) return HASH_DELETE_FAIL;//not have location in hash
		}
		else if (location < nodes[cur_id].ptr_disk)
		{
			pre_ptr = &nodes[cur_id].flist_pre;
			cur_id = nodes[cur_id].flist_pre;		
			if (cur_id == PTR_UNAVAILABLE) return HASH_DELETE_FAIL;//not have location in hash
		}
		else break;
	}

	assert(nodes[cur_id].ptr_disk == location);
	result_id = cur_id;

	if ((nodes[cur_id].flist_pre == PTR_UNAVAILABLE) && (nodes[cur_id].flist_suc == PTR_UNAVAILABLE))
	{
		*pre_ptr = PTR_UNAVAILABLE;
		return result_id;
	}

	if ((nodes[cur_id].flist_pre != PTR_UNAVAILABLE) && (nodes[cur_id].flist_suc == PTR_UNAVAILABLE))
	{
		*pre_ptr = nodes[cur_id].flist_pre;
		return result_id;
	}

	if ((nodes[cur_id].flist_pre ==PTR_UNAVAILABLE) && (nodes[cur_id].flist_suc != PTR_UNAVAILABLE))
	{
		*pre_ptr = nodes[cur_id].flist_suc;
		return result_id;
	}

	right_id = nodes[cur_id].flist_suc;
	right_left_id = right_id;
	while (nodes[right_left_id].flist_pre != PTR_UNAVAILABLE) right_left_id = nodes[right_left_id].flist_pre;
	nodes[right_left_id].flist_pre = nodes[cur_id].flist_pre;
	*pre_ptr = right_id;
	return result_id;
}

static int alloc_node_pool()
{
	int ret;
	if (node_pool_horizon == 0) 
	{
		ret = global_node_id;
		global_node_id = (global_node_id + 1) % NODE_POOL_SIZE;
	}
	else 
		ret = node_pool[--node_pool_horizon];
	return ret;
}

static void free_node_pool(int node_id)
{
	node_pool[node_pool_horizon] = node_id;
	node_pool_horizon = (node_pool_horizon + 1) % NODE_POOL_SIZE;
}

static int get_free_list(int slot_cnt)
{
	int i = slot_cnt;

	while (free_list[i] == PTR_UNAVAILABLE && i < FREE_LIST_LENGTH)	i++;
	if (i >= FREE_LIST_LENGTH) { printf("not have enough space at get_free_list\n"); return NOT_HAVE_ENOUGH_SPACE;} 

	int	node_id = free_list[i];
	free_list[i] = nodes[node_id].flist_suc;
	if (nodes[node_id].flist_suc != PTR_UNAVAILABLE)
		nodes[nodes[node_id].flist_suc].flist_pre = PTR_UNAVAILABLE;

	return node_id;
}

static void put_free_list(int node_id)
{
	int free_list_id = nodes[node_id].size > 160 ? 161 : nodes[node_id].size;

	nodes[node_id].flist_pre = PTR_UNAVAILABLE;
	nodes[node_id].flist_suc = free_list[free_list_id];
	if (nodes[node_id].flist_suc != PTR_UNAVAILABLE) nodes[nodes[node_id].flist_suc].flist_pre = node_id;
	free_list[free_list_id] = node_id;
}

static void delete_free_list_by_id(int node_id)
{
	int free_list_id = nodes[node_id].size > 160 ? 161 : nodes[node_id].size;
	int flist_pre = nodes[node_id].flist_pre;
	int flist_suc = nodes[node_id].flist_suc;

	if (flist_pre == PTR_UNAVAILABLE)
	{
		free_list[free_list_id] = flist_suc;
		if (flist_suc != PTR_UNAVAILABLE) nodes[flist_suc].flist_pre = PTR_UNAVAILABLE;
	}
	else
	{
		nodes[flist_pre].flist_suc = flist_suc;
		if (flist_suc != PTR_UNAVAILABLE) nodes[flist_suc].flist_pre = flist_pre;
	}
}

void disk_init()
{
	int i, node_id;

	nodes = malloc(sizeof(NODE) * NODE_MAX_CNT);
	for (i = 0; i < FREE_LIST_LENGTH; i++) free_list[i] = PTR_UNAVAILABLE;
	for (i = 0; i < HASH_LENGTH; i++) hash[i] = PTR_UNAVAILABLE;

	global_node_id = 0;
	node_pool_horizon = 0;

	node_id = alloc_node_pool();
	nodes[node_id].used = 0;
	nodes[node_id].size = (1 << 26);
	nodes[node_id].ptr_disk = 0;
	nodes[node_id].node_pre = nodes[node_id].node_suc = PTR_UNAVAILABLE;
	put_free_list(node_id);
}

int disk_alloc(int slot_cnt)
{
	if (slot_cnt > 160 || slot_cnt <= 0) return DISK_ALLOC_FAIL;
	if (free_list[slot_cnt] != PTR_UNAVAILABLE)/**************just equal to slot_cnt*****************/
	{
		int node_id = get_free_list(slot_cnt);
		nodes[node_id].used = 1;// size, ptr_disk, node_pre, node_suc are not change, flist_pre and flist_suc have changed at func:get_free_list
		hash_insert(nodes[node_id].ptr_disk, node_id);
		return nodes[node_id].ptr_disk;
	}
	else/*************bigger than slot_cnt**************/
	{
		int free_node_id = get_free_list(slot_cnt);
		if (free_node_id == NOT_HAVE_ENOUGH_SPACE) return DISK_ALLOC_FAIL;
		int node_id = alloc_node_pool(); 


		nodes[node_id].used = 1;
		nodes[node_id].size = slot_cnt;
		nodes[node_id].ptr_disk = nodes[free_node_id].ptr_disk;
		nodes[node_id].node_pre = nodes[free_node_id].node_pre;
		nodes[node_id].node_suc = free_node_id;

		nodes[free_node_id].used = 0;
		nodes[free_node_id].size -= slot_cnt;
		nodes[free_node_id].ptr_disk = nodes[free_node_id].ptr_disk + slot_cnt;
		if (nodes[free_node_id].node_pre !=	PTR_UNAVAILABLE) nodes[nodes[free_node_id].node_pre].node_suc = node_id;
		nodes[free_node_id].node_pre = node_id;
		//nodes[free_node_id].node_suc not change

		put_free_list(free_node_id);
		hash_insert(nodes[node_id].ptr_disk, node_id);

		return nodes[node_id].ptr_disk;
	}
}

void disk_free(int location)
{
	int node_id;

	node_id = hash_delete(location);
	if (node_id == HASH_DELETE_FAIL)
	{
		printf("hash delete fail \n");
		return;
	}

	int node_pre = nodes[node_id].node_pre;
	int node_suc = nodes[node_id].node_suc;

	if (node_pre != PTR_UNAVAILABLE && !nodes[node_pre].used)//free buddy to left
	{
		while (!nodes[node_pre].used)
		{
			nodes[node_id].used = 0;
			nodes[node_id].size += nodes[node_pre].size;
			nodes[node_id].ptr_disk = nodes[node_pre].ptr_disk;
			nodes[node_id].node_pre = nodes[node_pre].node_pre;
			//nodes[node_id].node_suc not change
			if (nodes[node_pre].node_pre != PTR_UNAVAILABLE)
				nodes[nodes[node_pre].node_pre].node_suc = node_id;
			delete_free_list_by_id(node_pre);
			free_node_pool(node_pre);
			node_pre = nodes[node_id].node_pre;
		}
	}
	else//free buddy to right
		if (node_suc != PTR_UNAVAILABLE && !nodes[node_suc].used)
		{
			while (!nodes[node_suc].used)
			{
				nodes[node_id].used = 0;
				nodes[node_id].size += nodes[node_suc].size;
				//nodes[node_id].ptr_disk not change
				//nodes[node_id].node_pre not change
				nodes[node_id].node_suc = nodes[node_suc].node_suc;
				if (nodes[node_suc].node_suc != PTR_UNAVAILABLE)
						nodes[nodes[node_suc].node_suc].node_pre = node_id;
				delete_free_list_by_id(node_suc);
				free_node_pool(node_suc);
				node_suc = nodes[node_id].node_suc;
			}
		}
		else nodes[node_id].used = 0;//free itself

	put_free_list(node_id);
}

